package br.com.rookgraph;

/**
 * Grafo com representação em armazenamento em Matiz.
 * 
 * @author Luan Pontes
 * @since 11-9-12
 *
 */
public class Graph {
	
	/**	associações entre vertices (Arestas) **/
	private int[][] edges;
	
	/**	Número de Vertices **/
	private int order;
	
	public Graph(int order){
		this.order = order;
		this.edges = new int[order][order];
	}
	
	/**
	 * Adiciona uma associação entre vertices.
	 * 
	 * @param origin origem
	 * @param target destino
	 * @param value  valor associação
	 * 
	 */
	public void addEdge(int origin, int target, int value){
		if(isValid(origin, target)){
			setMatriz(origin, target, value);
			setMatriz(target, origin, value);
		}
	}
	/**
	 * Remove uma associação entre vertices.
	 * 
	 * @param origin origem
	 * @param target destino
	 * 
	 */
	public void removeEdge(int origin, int target){
		if(isValid(origin, target)){
			setMatriz(origin, target, 0);
			setMatriz(target, origin, 0);
		}
	}

	/**
	 * Verifica a existencia de uma associação.
	 * 
	 * @param origin origem
	 * @param target destino
	 */
	public boolean hasEdge(int origin, int target){
		return isValid(origin, target) && getMatix(origin, target) != 0; 
	}
	
	/** Recupera o valor de uma Aresta.
	 * @param origin
	 * @param target
	 * @return valor da Aresta
	 */
	public int getEdge(int origin, int target){
		return isValid(origin, target) ? getMatix(origin, target) : 0;
	}
	
	/**
	 * Mostra na saída padrão as associações do Grafo.
	 */
	public void showEdges(){
		for (int i = 0; i < this.edges.length; i++) {
			for (int j = 0; j < this.edges[0].length; j++) {
				
				if(this.edges[i][j] != 0 ){
					System.out.println( (i+1)+ "<--("+this.edges[i][j]+")-->"+(j+1));
				}
				
			}
		}
	}
	
	/**
	 * Mostra na saída padrão as associações do Grafo em 
	 * forma de matriz.
	 */
	public void showMatix(){
		System.out.print("   ");
		for (int i = 0; i < this.edges.length; i++) {
			System.out.print("|_"+(i+1)+"_");
		}
		for (int i = 0; i < this.edges.length; i++) {
			System.out.print("\n "+(i+1));
			for (int j = 0; j < this.edges[0].length; j++) {
					
				int value = this.edges[i][j];
				System.out.print(" | "+ ( value != 0 ? value : " "));
			}
		}
	}
	
	/**
	 * @return ordem do grafo.
	 */
	public int getOrder(){
		return this.order; 
	}
	
	/**
	 * Retorna o ALFA da aresta, ou seja, o número de 
	 * branchs que a aresta incide. 
	 * 
	 * @param oring
	 * @param target
	 * @return
	 */
	public int alfa(int oring, int target){
		int quantBranch = 0;
		
		quantBranch += grau(oring) > 2 ? 1 : 0;
		quantBranch += grau(target) > 2 ? 1 : 0;
		
		return quantBranch;
	}
	
	/**
	 * Retorna o sigma de uma aresta, ou seja, 
	 * o somatorio de dos graus que a aresta incide 
	 * menos a própria aresta em questão.
	 * 
	 * @param oring
	 * @param target
	 * @return
	 */
	public int sigma(int oring, int target){
		return grau(oring) + grau(target) - 2;
	}
	
	/**
	 * Retorna o grau do vertice passado, ou seja, o 
	 * número de aresta que o vertice possui.
	 * @param v
	 * @return
	 */
	private int grau(int v) {
		return this.getAdjacentes(v).length;
	}
	
	public int[] getBranchs() {
		int[] branches = new int[this.order];
		int iBranches = 0;
		for (int i = 1; i <= this.order; i++) {
			if(this.grau(i) > 2){
				branches[iBranches++] = i;
			}
		}
		
		int[] branchesResult = new int[iBranches];
		System.arraycopy(branches, 0, branchesResult, 0, iBranches);
		return branchesResult;
	}
	
	
	/**
	 * Método gera uma Arvore apartir do grafo. 
	 * Recebe um né que será usado como 'raiz', dependendo da 
	 * raiz a arvore tera uma formato diferente.
	 * 
	 *   TODO verificar se isso acontece em para qualquer grafo.
 	 *
	 * @param graphTree grafor retornado que coterá a 'arvore'.
	 * @param root raiz utilizada no grafo.
	 * 
	 * @return graphTree representado a arvore gerada.
	 */
	public Graph getTree(Graph graphTree, final int root){
		
		int[] adjacents = getAdjacentes(root);
		
		for (int vAdj = 0; vAdj < adjacents.length; vAdj++) {
			boolean hasTree = false;
				
				for (int vTree = 1; vTree <= this.order; vTree++) {
					
					if(graphTree.hasEdge(adjacents[vAdj], vTree)){
						hasTree = true;
						break;
					}
				}
				
				if(!hasTree){
					graphTree.addEdge(root, adjacents[vAdj], getMatix(root, adjacents[vAdj]));
					getTree(graphTree, adjacents[vAdj]); 
				}
				
		}
		return graphTree;
	}

	//	TODO: Observar a frequência de uso deste método
	//	se for muito frequente, seria melhor pensar em uma
	//	nova representação para o grafo.
	public int[] getAdjacentes(int v) {
		int[] lineMatrix = new int[order];
		int count = 0;
		for (int j = 0; j < order; j++) {
			
			if(this.edges[v-1][j] != 0){
				lineMatrix[count++] = j+1;
			}
			
		}
		
		int[] adjacents = new int[count];
		System.arraycopy(lineMatrix ,0,adjacents,0,count);
		
		return adjacents;
	}
	
	
	
	public int[] reached(int root, int[] listCut){
		
		int[] adjacents = getAdjacentes(root);
		int count = posiList(listCut);
		listCut[count] = root;
		for (int vAdj : adjacents) {
			if(!this.conteins(vAdj, listCut)){
				reached(vAdj, listCut);
			}
		}
		count = posiList(listCut);
		int[] newListCut = new int[count];
		System.arraycopy(listCut, 0, newListCut, 0, count);
		
		return newListCut;
	}
	
	public boolean conteins(int v, int[] list) {
		for (int i : list) {
			if(i == v) return true;
		}
		return false;
	}
	
	private int posiList(int[] list){
		int i;
		for ( i = 0; i < list.length; i++) {
			if(list[i] == 0){
				return i;
			}
		}
		return i;
	}
	
	
	
	
	/**
	 * Verifica se a origin e target são validos, 
	 * se não lança uma  IllegalArgumentException.
	 * @param origin
	 * @param target
	 * @return
	 */
	private boolean isValid(int origin, int target) {
		if((origin > 0 && origin <= order) || (target > 0 && target <= order)){
			return true;
		}
		throw new IllegalArgumentException("Origin ("+origin+") or Target("+target+") invalid!( < 0 or > ordem )");
	}
	
	private void setMatriz(int origin, int target, int value) {
		this.edges[origin-1][target-1] = value;
	}
	
	public int getMatix(int origin, int target) {
		return this.edges[origin-1][target-1];
	}
	
	public int[][] edges(){
		return this.edges;
	}
	
}

